This invention relates to an access and apparatus for selectively extracting or updating subarrays of a larger array stored in a modified work organized random access memory system, and more particularly, relates to the modifications to a conventional work organized memory used for image processing.
As understood, a digital image is considered to be a two-dimensional array of image points, each of which comprises an integer or a set of integers. Image manipulation ideally subsumes the capability of storing an image array in a memory and operating upon selected clusters of points simultaneously, such as sequences of points in a single row of the array and points within a small rectangular area. This imposes the constraint that the memory must allow all points in any selected cluster to be accessed in one memory cycle. If any desired combination of points in the array could be accessed simultaneously from a bit addressable memory, then storage and retrieval of clusters of image points would pose no problem. However, because digital images form large arrays, only word organized memories are economically available. A conventional word organized memory includes a plurality of randomly accessible "words" of storage locations, each word of which can store a cluster of image points. However, it is necessary to modify the accessing mechanism of this conventional memory in order to permit access to clusters of image points when the points are not all in the same word of storage.
An image can be represented by a M .times. N array I(*,*) of image points, where each point I(i,j) for O.ltoreq.i&lt;M and O.ltoreq.j&lt;N is an integer or a set of integers which represents the color and intensity of a portion of the image. For simplicity, attention can be restricted to black/white images, for which I(i,j) is a single bit of information. Typically, I(i,j)=1 represents a black area of the image, and I(i,j)=0 represents a white area.
Images are most commonly generated by scanning pictorial data such as 8 1/2 inch .times. 14 inch documents. Thereafter, they can be stored, viewed from a display, transmitted, or printed. Since most scanners and printers process an image from top to bottom and from left to right, images are normally transmitted in the standard "row major" sequence: I(0,0), I(0,1), . . . , I(0,N-1), I(1,0), . . . , I(M-1, N-1). Therefore, a memory system for image processing operations should at least permit simultaneous access to a number of adjacent image points on a single row of I(*,*). This would permit the image or a partial image to be transferred rapidly into and out of the memory system, with many image points in each row being transferred simultaneously.
It is also desireable to access rectangular blocks of points within the image to accomodate another class of image processing operations, such as block insertion, block extraction, and contour following. For example, it may be desirable to add alphanumeric characters to the image from a stored dictionary, which dictionary includes a predefined bit array for each character. Similarly, it may be desirable to delete or edit characters or other rectangular blocks from an image. Lastly, algorithms for locating the contours of objects in the image involve moving a cursor from one image point to another along a border or boundary of an object. The contour following algorithms require rapid access to an image point and a plurality of its near neighbors, which together constitute a block of image points.
Typically, a word organized random acess memory comprises a plurality of memory modules, each module being a storage device with a plurality of randomly accessible storage cells. Although each cell is able to store an image point which comprise a single bit of information, only one cell in a module can be accessed (read from or stored into) at a time. The accessing mechanism of a conventional word organized random acess memory provides a single cell address to all of its constituent memory modules, so that the ith cell in one module can be accessed only in conjunction with the ith cell of all other modules. (These cells together comprise the ith word of the memory). A conventional word organized random access memory thus provides access to a cluster of image points only if they are all stored in the same word of the memory. However, a suitable modification of the accessing mechanism for a word organized memory can permit acess to any desired cluster of image points, provided each module stores at most one point in the cluster.
As stated previously, a memory system is desired which permits access to horizontal sequences and rectangular blocks of image points. Therefore, it is necessary to determine a method for distributing image points among memory modules which places the elements of horizontal sequences in distinct memory modules and which also places the elements of rectangular blocks in distinct memory modules. Relatedly, it is necessary to devise addressing circuitry which permits simultaneous access to all elements of the horizontal sequences or rectangular blocks. Lastly, it is necessary to design circuitry which arranges the elements of the sequences or blocks accessed into a convenient order, such as row major order.